// biome-ignore-all lint/style/noNonNullAssertion: 整个文件暂时忽略此规则
import { describe, expect, test } from 'vitest';
import {
  cloneTree,
  findNodeById,
  flattenTree,
  formatStdNode,
  getTreeDepth,
  getTreeLeafs,
  traverseTree,
  treeNodeToMap,
} from '../../src/hammer/array.mts';

/**
 * 树节点
 */
type Node<T extends Record<string, unknown>> = T & {
  parent: Node<T> | null;
  children: Node<T>[] | null;
  id: string;
};

// 创建测试用的树结构
const createTestTree = () => {
  /*
  创建如下结构的树:
        1
      /   \
     2     3
    / \   / \
   4   5 6   7
  */
  const node4: Node<{ name: string }> = {
    name: 'node4',
    parent: null,
    children: null,
    id: '4',
  };

  const node5: Node<{ name: string }> = {
    name: 'node5',
    parent: null,
    children: null,
    id: '5',
  };

  const node6: Node<{ name: string }> = {
    name: 'node6',
    parent: null,
    children: null,
    id: '6',
  };

  const node7: Node<{ name: string }> = {
    name: 'node7',
    parent: null,
    children: null,
    id: '7',
  };

  const node2: Node<{ name: string }> = {
    name: 'node2',
    parent: null,
    children: [node4, node5],
    id: '2',
  };

  const node3: Node<{ name: string }> = {
    name: 'node3',
    parent: null,
    children: [node6, node7],
    id: '3',
  };

  const node1: Node<{ name: string }> = {
    name: 'node1',
    parent: null,
    children: [node2, node3],
    id: '1',
  };

  // 设置parent引用
  node2.parent = node1;
  node3.parent = node1;
  node4.parent = node2;
  node5.parent = node2;
  node6.parent = node3;
  node7.parent = node3;

  return node1;
};

// 创建空子节点的树结构
const createTreeWithEmptyChildren = () => {
  const node: Node<{ name: string }> = {
    name: 'root',
    parent: null,
    children: [],
    id: '1',
  };
  return node;
};

// 创建单节点树
const createSingleNodeTree = () => {
  const node: Node<{ name: string }> = {
    name: 'single',
    parent: null,
    children: null,
    id: '1',
  };
  return node;
};

// 创建不平衡树
const createUnbalancedTree = () => {
  const node8: Node<{ name: string }> = {
    name: 'node8',
    parent: null,
    children: null,
    id: '8',
  };

  const node9: Node<{ name: string }> = {
    name: 'node9',
    parent: null,
    children: null,
    id: '9',
  };

  const node10: Node<{ name: string }> = {
    name: 'node10',
    parent: null,
    children: null,
    id: '10',
  };

  const node5: Node<{ name: string }> = {
    name: 'node5',
    parent: null,
    children: [node8, node9, node10],
    id: '5',
  };

  const node2: Node<{ name: string }> = {
    name: 'node2',
    parent: null,
    children: [node5],
    id: '2',
  };

  const node1: Node<{ name: string }> = {
    name: 'node1',
    parent: null,
    children: [node2],
    id: '1',
  };

  // 设置parent引用
  node2.parent = node1;
  node5.parent = node2;
  node8.parent = node5;
  node9.parent = node5;
  node10.parent = node5;

  return node1;
};

describe('树结构工具函数', () => {
  describe('traverseTree', () => {
    test('遍历所有节点', () => {
      const tree = createTestTree();
      const visitedNodes: string[] = [];

      traverseTree(tree, (node) => {
        visitedNodes.push(node.name as string);
      });

      expect(visitedNodes).toHaveLength(7);
      expect(visitedNodes).toEqual([
        'node1',
        'node2',
        'node4',
        'node5',
        'node3',
        'node6',
        'node7',
      ]);
    });

    test('遍历只有一个节点的树', () => {
      const tree = createSingleNodeTree();
      const visitedNodes: string[] = [];

      traverseTree(tree, (node) => {
        visitedNodes.push(node.name as string);
      });

      expect(visitedNodes).toHaveLength(1);
      expect(visitedNodes).toEqual(['single']);
    });

    test('遍历空子节点的树', () => {
      const tree = createTreeWithEmptyChildren();
      const visitedNodes: string[] = [];

      traverseTree(tree, (node) => {
        visitedNodes.push(node.name as string);
      });

      expect(visitedNodes).toHaveLength(1);
      expect(visitedNodes).toEqual(['root']);
    });

    test('遍历children为null的节点', () => {
      const tree: Node<{ name: string }> = {
        name: 'test',
        parent: null,
        children: null,
        id: '1',
      };

      const visitedNodes: string[] = [];
      traverseTree(tree, (node) => {
        visitedNodes.push(node.name as string);
      });

      expect(visitedNodes).toHaveLength(1);
      expect(visitedNodes).toEqual(['test']);
    });
  });

  describe('getTreeDepth', () => {
    test('计算树的深度', () => {
      const tree = createTestTree();
      expect(getTreeDepth(tree)).toBe(3);
    });

    test('计算单节点树的深度', () => {
      const tree = createSingleNodeTree();
      expect(getTreeDepth(tree)).toBe(1);
    });

    test('计算不平衡树的深度', () => {
      const tree = createUnbalancedTree();
      expect(getTreeDepth(tree)).toBe(4);
    });

    test('计算空子节点树的深度', () => {
      const tree = createTreeWithEmptyChildren();
      expect(getTreeDepth(tree)).toBe(1);
    });

    test('处理children为null的节点', () => {
      const tree: Node<{ name: string }> = {
        name: 'test',
        parent: null,
        children: null,
        id: '1',
      };
      expect(getTreeDepth(tree)).toBe(1);
    });
  });

  describe('flattenTree', () => {
    test('扁平化树结构', () => {
      const tree = createTestTree();
      const flatNodes = flattenTree(tree);

      expect(flatNodes).toHaveLength(7);
      const nodeNames = flatNodes.map((node) => node.name as string);
      expect(nodeNames).toEqual([
        'node1',
        'node2',
        'node4',
        'node5',
        'node3',
        'node6',
        'node7',
      ]);
    });

    test('扁平化单节点树', () => {
      const tree = createSingleNodeTree();
      const flatNodes = flattenTree(tree);

      expect(flatNodes).toHaveLength(1);
      expect(flatNodes[0].name).toBe('single');
    });

    test('扁平化空子节点树', () => {
      const tree = createTreeWithEmptyChildren();
      const flatNodes = flattenTree(tree);

      expect(flatNodes).toHaveLength(1);
      expect(flatNodes[0].name).toBe('root');
    });

    test('扁平化children为null的节点', () => {
      const tree: Node<{ name: string }> = {
        name: 'test',
        parent: null,
        children: null,
        id: '1',
      };
      const flatNodes = flattenTree(tree);

      expect(flatNodes).toHaveLength(1);
      expect(flatNodes[0].name).toBe('test');
    });
  });

  describe('cloneTree', () => {
    test('克隆树结构', () => {
      const tree = createTestTree();
      const clonedTree = cloneTree(tree);

      expect(clonedTree).not.toBe(tree);
      expect(clonedTree.name).toBe(tree.name);
      expect(clonedTree.children).toHaveLength(2);
      expect(clonedTree.children![0]).not.toBe(tree.children![0]);
      expect(clonedTree.children![0].name).toBe(tree.children![0].name);
    });

    test('克隆单节点树', () => {
      const tree = createSingleNodeTree();
      const clonedTree = cloneTree(tree);

      expect(clonedTree).not.toBe(tree);
      expect(clonedTree.name).toBe('single');
      expect(clonedTree.children).toBeNull();
    });

    test('克隆空子节点树', () => {
      const tree = createTreeWithEmptyChildren();
      const clonedTree = cloneTree(tree);

      expect(clonedTree).not.toBe(tree);
      expect(clonedTree.name).toBe('root');
      expect(clonedTree.children).toEqual([]);
    });

    test('克隆children为null的节点', () => {
      const tree: Node<{ name: string }> = {
        name: 'test',
        parent: null,
        children: null,
        id: '1',
      };
      const clonedTree = cloneTree(tree);

      expect(clonedTree).not.toBe(tree);
      expect(clonedTree.name).toBe('test');
      expect(clonedTree.children).toBeNull();
    });
  });

  describe('findNodeById', () => {
    test('按ID查找节点', () => {
      const tree = createTestTree();
      const foundNode = findNodeById('4', tree);

      expect(foundNode).toBeDefined();
      expect(foundNode?.name).toBe('node4');
      expect(foundNode?.id).toBe('4');
    });

    test('查找不存在的节点', () => {
      const tree = createTestTree();
      const foundNode = findNodeById('999', tree);

      expect(foundNode).toBeUndefined();
    });

    test('在单节点树中查找', () => {
      const tree = createSingleNodeTree();
      const foundNode = findNodeById('1', tree);

      expect(foundNode).toBeDefined();
      expect(foundNode?.name).toBe('single');
    });

    test('在空子节点树中查找', () => {
      const tree = createTreeWithEmptyChildren();
      const foundNode = findNodeById('1', tree);

      expect(foundNode).toBeDefined();
      expect(foundNode?.name).toBe('root');
    });

    test('在children为null的节点中查找', () => {
      const tree: Node<{ name: string }> = {
        name: 'test',
        parent: null,
        children: null,
        id: '1',
      };
      const foundNode = findNodeById('1', tree);

      expect(foundNode).toBeDefined();
      expect(foundNode?.name).toBe('test');
    });
  });

  describe('treeNodeToMap', () => {
    test('将树节点转换为Map', () => {
      const tree = createTestTree();
      const nodeMap = treeNodeToMap(tree);

      expect(nodeMap.size).toBe(7);
      expect(nodeMap.get('1')?.name).toBe('node1');
      expect(nodeMap.get('2')?.name).toBe('node2');
      expect(nodeMap.get('3')?.name).toBe('node3');
      expect(nodeMap.get('4')?.name).toBe('node4');
      expect(nodeMap.get('5')?.name).toBe('node5');
      expect(nodeMap.get('6')?.name).toBe('node6');
      expect(nodeMap.get('7')?.name).toBe('node7');
    });

    test('转换单节点树', () => {
      const tree = createSingleNodeTree();
      const nodeMap = treeNodeToMap(tree);

      expect(nodeMap.size).toBe(1);
      expect(nodeMap.get('1')?.name).toBe('single');
    });

    test('转换空子节点树', () => {
      const tree = createTreeWithEmptyChildren();
      const nodeMap = treeNodeToMap(tree);

      expect(nodeMap.size).toBe(1);
      expect(nodeMap.get('1')?.name).toBe('root');
    });

    test('转换children为null的节点', () => {
      const tree: Node<{ name: string }> = {
        name: 'test',
        parent: null,
        children: null,
        id: '1',
      };
      const nodeMap = treeNodeToMap(tree);

      expect(nodeMap.size).toBe(1);
      expect(nodeMap.get('1')?.name).toBe('test');
    });
  });

  describe('getTreeLeafs', () => {
    test('获取所有叶子节点', () => {
      const tree = createTestTree();
      const leafNodes = getTreeLeafs(tree);

      expect(leafNodes).toHaveLength(4);
      const leafNames = leafNodes.map((node) => node.name as string);
      expect(leafNames).toEqual(['node4', 'node5', 'node6', 'node7']);
    });

    test('单节点树的叶子节点', () => {
      const tree = createSingleNodeTree();
      const leafNodes = getTreeLeafs(tree);

      expect(leafNodes).toHaveLength(1);
      expect(leafNodes[0].name).toBe('single');
    });

    test('空子节点树的叶子节点', () => {
      const tree = createTreeWithEmptyChildren();
      const leafNodes = getTreeLeafs(tree);

      // 空子节点数组被视为有子节点，因此返回空数组
      expect(leafNodes).toHaveLength(0);
    });

    test('处理children为null的节点', () => {
      const tree: Node<{ name: string }> = {
        name: 'test',
        parent: null,
        children: null,
        id: '1',
      };
      const leafNodes = getTreeLeafs(tree);

      expect(leafNodes).toHaveLength(1);
      expect(leafNodes[0].name).toBe('test');
    });

    test('不平衡树的叶子节点', () => {
      const tree = createUnbalancedTree();
      const leafNodes = getTreeLeafs(tree);

      expect(leafNodes).toHaveLength(3);
      const leafNames = leafNodes.map((node) => node.name as string);
      expect(leafNames).toEqual(['node8', 'node9', 'node10']);
    });

    test('深层嵌套树的叶子节点', () => {
      const deepTree: Node<{ name: string; id: string }> = {
        id: '1',
        name: 'level1',
        parent: null,
        children: [
          {
            id: '2',
            name: 'level2',
            parent: null,
            children: [
              {
                id: '3',
                name: 'level3',
                parent: null,
                children: [
                  {
                    id: '4',
                    name: 'level4',
                    parent: null,
                    children: null,
                  },
                ],
              },
            ],
          },
        ],
      };
      deepTree.children![0].parent = deepTree;
      deepTree.children![0].children![0].parent = deepTree.children![0];
      deepTree.children![0].children![0].children![0].parent =
        deepTree.children![0].children![0];

      const leafNodes = getTreeLeafs(deepTree);

      expect(leafNodes).toHaveLength(1);
      expect(leafNodes[0].id).toBe('4');
      expect(leafNodes[0].name).toBe('level4');
    });

    test('叶子节点保持原始属性', () => {
      const tree: Node<{ id: string; value: number; active: boolean }> = {
        id: 'root',
        value: 100,
        active: true,
        parent: null,
        children: [
          {
            id: 'leaf1',
            value: 50,
            active: false,
            parent: null,
            children: null,
          },
          {
            id: 'leaf2',
            value: 75,
            active: true,
            parent: null,
            children: null,
          },
        ],
      };
      tree.children![0].parent = tree;
      tree.children![1].parent = tree;

      const leafNodes = getTreeLeafs(tree);

      expect(leafNodes).toHaveLength(2);
      expect(leafNodes[0].value).toBe(50);
      expect(leafNodes[0].active).toBe(false);
      expect(leafNodes[1].value).toBe(75);
      expect(leafNodes[1].active).toBe(true);
    });
  });

  describe('formatStdNode', () => {
    test('格式化标准树节点', () => {
      type TestNode = {
        id: string;
        name: string;
        children: TestNode[];
      };

      const sourceNode: TestNode = {
        id: '1',
        name: 'root',
        children: [
          {
            id: '2',
            name: 'child1',
            children: [],
          },
          {
            id: '3',
            name: 'child2',
            children: [],
          },
        ],
      };

      const formattedNode = formatStdNode(sourceNode);

      expect(formattedNode.id).toBe('1');
      expect(formattedNode.name).toBe('root');
      expect(formattedNode.children).toHaveLength(2);
      expect(formattedNode.children?.[0].id).toBe('2');
      expect(formattedNode.children?.[0].name).toBe('child1');
      expect(formattedNode.children?.[0].children).toHaveLength(0);
      expect(formattedNode.children?.[1].id).toBe('3');
      expect(formattedNode.children?.[1].name).toBe('child2');
      expect(formattedNode.children?.[1].children).toHaveLength(0);
      expect(formattedNode.children?.[0].parent).toBe(formattedNode);
      expect(formattedNode.children?.[1].parent).toBe(formattedNode);
    });

    test('格式化没有子节点的节点', () => {
      type TestNode = {
        id: string;
        name: string;
        value: number;
        children: TestNode[];
      };

      const sourceNode: TestNode = {
        id: '1',
        name: 'root',
        value: 42,
        children: [],
      };

      const formattedNode = formatStdNode(sourceNode);

      expect(formattedNode.id).toBe('1');
      expect(formattedNode.name).toBe('root');
      expect((formattedNode as { value: number }).value).toBe(42);
      expect(formattedNode.children).toHaveLength(0);
    });

    test('格式化嵌套更深的树', () => {
      type TestNode = {
        id: string;
        name: string;
        children: TestNode[];
      };

      const sourceNode: TestNode = {
        id: '1',
        name: 'root',
        children: [
          {
            id: '2',
            name: 'child',
            children: [
              {
                id: '3',
                name: 'grandchild',
                children: [],
              },
            ],
          },
        ],
      };

      const formattedNode = formatStdNode<TestNode>(sourceNode);

      expect(formattedNode.id).toBe('1');
      expect(formattedNode.name).toBe('root');
      expect(formattedNode.children).toHaveLength(1);
      expect(formattedNode.children?.[0].id).toBe('2');
      expect(formattedNode.children?.[0].name).toBe('child');
      expect(formattedNode.children?.[0].children).toHaveLength(1);
      expect(formattedNode.children?.[0].children?.[0].id).toBe('3');
      expect(formattedNode.children?.[0].children?.[0].name).toBe('grandchild');
      expect(formattedNode.children?.[0].children?.[0].children).toHaveLength(
        0,
      );
      expect(formattedNode.children?.[0].parent).toBe(formattedNode);
      expect(formattedNode.children?.[0].children?.[0].parent).toBe(
        formattedNode.children?.[0],
      );
    });
  });
});
